package dp;

/**
 * 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
 */
public class leetCode221_maximalSquare {
    // dp[i][j] 表示下标为i,j 值为'1'时的最大面积
    public int maximalSquare(char[][] matrix) {

        if(matrix == null || matrix.length == 0) return 0;
        int max = 0;
        int n = matrix.length;
        int m = matrix[0].length;
        int[][] dp = new int[n][m];
        for (int i = 0; i < n; i++) {
            if(matrix[i][0] == '1') {
                dp[i][0] = 1;
                max = Math.max(max, dp[i][0]);
            }
        }
        for (int i = 0; i < m; i++) {
            if(matrix[0][i] == '1') {
                dp[0][i] = 1;
                max = Math.max(max,dp[0][i]);
            }
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if(matrix[i][j] == '1'){
                    dp[i][j] = Math.min(dp[i - 1][j],Math.min(dp[i][j - 1],dp[i - 1][j - 1])) + 1;
                    max = Math.max(dp[i][j],max);
                }
            }
        }
        return max * max;
    }
}
